package day03

// day03
//
// 491. 非递减子序列
//
// https://leetcode.cn/problems/non-decreasing-subsequences/
//
// ```go
func findSubsequences(nums []int) [][]int {
	ans := make([][]int, 0)
	var dfs func(path []int, pos int)
	dfs = func(path []int, pos int) {
		if len(path) >= 2 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
		}
		mp := map[int]bool{}
		for i := pos; i < len(nums); i++ {
			if _, ok := mp[nums[i]]; ok {
				continue
			}
			if len(path) == 0 || path[len(path)-1] <= nums[i] {
				path = append(path, nums[i])
				mp[nums[i]] = true
				dfs(path, i+1)
				path = path[:len(path)-1]
				mp[nums[i]] = false
			}
		}
	}
	dfs([]int{}, 0)
	return ans
}

//```

// 46. 全排列
//
// https://leetcode.cn/problems/permutations/
//
// ```go
func permute(nums []int) [][]int {
	ans := make([][]int, 0)
	mp := map[int]bool{}
	var dfs func(path []int)
	dfs = func(path []int) {
		if len(path) == len(nums) {
			tmp := make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
		}
		for i := 0; i < len(nums); i++ {
			if _, ok := mp[nums[i]]; ok {
				continue
			}
			path = append(path, nums[i])
			mp[nums[i]] = true
			dfs(path)
			path = path[:len(path)-1]
			// mp[nums[i]] = false
			delete(mp, nums[i])
		}
	}
	dfs([]int{})
	return ans
}

//```

// 47. 全排列 II
//
// https://leetcode.cn/problems/permutations-ii/
//
// ```go
func permuteUnique(nums []int) [][]int {
	ans := make([][]int, 0)
	mp := map[int]bool{}
	var dfs func(path []int)
	dfs = func(path []int) {
		if len(path) == len(nums) {
			tmp := make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
		}
		mmp := map[int]bool{}
		for i := 0; i < len(nums); i++ {
			if _, ok := mp[i]; ok {
				continue
			}
			if _, ok := mmp[nums[i]]; ok {
				continue
			}
			path = append(path, nums[i])
			mp[i] = true
			mmp[nums[i]] = true
			dfs(path)
			path = path[:len(path)-1]
			delete(mp, i)
			mmp[nums[i]] = true
		}
	}
	dfs([]int{})
	return ans
}

//```
